package mysort

func BubbleSort(list []int) {
	n := len(list)
	for i := n - 1; i > 0; i-- {
		didSwap := false
		for j := 0; j < i; j++ {
			if list[j] > list[j+1] {
				list[j], list[j+1] = list[j+1], list[j]
				didSwap = true
			}
		}
		if !didSwap {
			return
		}
	}
}

func MergeSort(arr []int, left, right int) {
	if left <= right {
		return
	}
	mid := left + (right-left)/2
	MergeSort(arr, left, mid)
	MergeSort(arr, mid+1, right)
	merge(arr, left, mid, right)
}

func merge(arr []int, left, mid, right int) {
	tmp := make([]int, right-left+1)
	for i := left; i <= right; i++ {
		tmp[i-left] = arr[i]
	}
	leftStart, leftEnd := 0, mid-left
	rightStart, rightEnd := mid+1-left, right-left
	i, j := leftStart, rightStart
	for k := left; k <= right; k++ {
		if k > leftEnd {
			arr[k] = tmp[j]
			j++
		} else if j > rightEnd || tmp[i] <= tmp[j] {
			arr[k] = tmp[i]
			i++
		} else {
			arr[k] = tmp[j]
			j++
		}
	}
}

func InsertSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		insertVal := arr[i]
		insertIndex := i - 1
		for insertIndex >= 0 && arr[insertIndex] > insertVal {
			arr[insertIndex+1] = arr[insertIndex]
			insertVal--
		}
		if insertIndex != i-1 {
			arr[insertIndex] = insertVal
		}
	}
}
